package backTrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

import utils.linkListUtil;

public class letterCombinations {
    List<String> list = new ArrayList<>();
    HashMap<Integer,List<Character>> map = new HashMap<>();
    char[][] phone = {{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{},{},{},{'s',},{'v',},{}};
    public List<String> letterCombinations(String digits) {
        char[] arr = digits.toCharArray();
        if (arr.length==0) {
            return list;
        }
        map.put(2, new ArrayList<>(Arrays.asList('a','b','c')));
        map.put(3, new ArrayList<>(Arrays.asList('d','e','f')));
        map.put(4, new ArrayList<>(Arrays.asList('g','h','i')));
        map.put(5, new ArrayList<>(Arrays.asList('j','k','l')));
        map.put(6, new ArrayList<>(Arrays.asList('m','n','o')));
        map.put(7, new ArrayList<>(Arrays.asList('p','q','r','s')));
        map.put(8, new ArrayList<>(Arrays.asList('t','u','v')));
        map.put(9, new ArrayList<>(Arrays.asList('w','x','y','z')));
        backTrack(arr, new ArrayList<Character>(), 0);
        return list;
        
    }
    public void backTrack(char[] arr,List<Character> subList,int pos){
        if (pos==arr.length) {
            StringBuffer stringBuffer = new StringBuffer(list.size());
            for(Character c: subList){
                stringBuffer.append(c);
            }
            list.add(stringBuffer.toString());
            return;
        }
        //必须选
        List<Character> phone = map.get(arr[pos]-'a');
        for(Character c: phone){
            subList.add(c);
            backTrack(arr, subList, pos+1);
            subList.remove(subList.size()-1);
        }

    }
    public static void main(String[] args) {
        
    }
}
